package com.qilinreal.app;

import java.util.*;
import java.io.*;

public class GDBScan {
	public static double eps = 20;
	public static int minpts = 20;		// not used in this algorithm

	static void LOG(String msg, Object...args) {
		System.out.println(String.format(msg, args));
	}

	static long preTime = new Date().getTime();
	static long markTime() {
		long pre = preTime;
		preTime = new Date().getTime();
		return preTime - pre;
	}
	static void LOG() {
		System.out.println(new Date());
	}

	public static void main(String[] args) throws Exception {
		LOG(new Date()+"\tProgram Start.");
		LOG(System.getProperty("user.dir"));
		LOG("eps: %.2f, minpts: %d", eps, minpts);
		String filePath = "/mnt/c/Users/qilin/Desktop/java/points.in";
		LOG("Reading from file: %s...", filePath);
		Point points[] = readCSV(filePath);
		LOG("Points count: %d", points.length);
		LOG("Marking all points as unvisited...");
		// DO NOTHING
		LOG("CLUSTING...");
		// clusting
		markTime();
		GDBScan(points);
		LOG("Cost time: %d", markTime());
		LOG("Groups: %d", Group.groups.size());
		LOG("saving...");
		save();
		LOG("finished.");
	}

	static void save() throws Exception {
		FileOutputStream fos = new FileOutputStream(new File("./points.out"));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(fos));
		int i=1;
		for(Group g : Group.groups) {
			for(Point p : g.points) {
				bw.write(String.format("%f,%f,%d", p.d[0], p.d[1], i));
				bw.newLine();
			}
			i++;
		}
		bw.flush();
		bw.close();
		fos.close();
	}

	static Point[] readCSV(String filePath) throws IOException {
		List<Point> ret = new LinkedList<>();

		FileInputStream fis = new FileInputStream(new File(filePath));
		BufferedReader br = new BufferedReader(new InputStreamReader(fis, "UTF-8"));
		String line = null;
		while ((line = br.readLine()) != null) {
			try {
				String[] s = line.split(",");
				double[] d = new double[2];
				d[0] = Double.parseDouble(s[0]);
				d[1] = Double.parseDouble(s[1]);
				Point p = new Point(d);
				ret.add(p);
			} catch (NumberFormatException e) {}
		}
		fis.close();
		return ret.toArray(new Point[0]);
	}

	static void GDBScan(Point points[]) {
		for(int i=0; i<points.length; i++) {
			points[i].assigned = true;
		}
		for(Point p : points) {
			Group g = null;
			if((g = Group.cover(p, eps)) != null) {
				g.append(p);
			} else if((g = Group.cover2(p, eps)) != null) {
				p.assigned = false;
			} else {
				Group.newGroup(p, eps);
			}
		}
		for(Point p : points) {
			if(p.assigned) {
				continue;
			}
			Group g = null;
			if((g = Group.cover(p, eps)) != null) {
				g.append(p);
			} else {
				Group.newGroup(p, eps);
			}
		}
	}
}

class Point {
	public double[] d;
	boolean assigned = true;
	public Point(double[] d) throws NullPointerException {
		Util.assume(d.length != 0);
		this.d = d;
	}
	public static int length(Point points[]) {
		if(points == null) {
			return 0;
		}
		return points.length;
	}

	// Euler
	public static double distance(Point p1, Point p2) {
		double d = 0;
		if(p1.d.length != p2.d.length) {
			return 0;
		}
		for(int i=0; i<p1.d.length; i++) {
			d += (p1.d[i]-p2.d[i]) * (p1.d[i]-p2.d[i]);
		}
		return Math.sqrt(d);
	}
}

class Group {
	public List<Point> points;
	public Point core;
	public void append(Point p) {
		points.add(p);
	}
	public Group[] nearbyGroups(double eps) {
		List<Group> ret = new ArrayList<>();
		for(Group g : groups) {
			if(g.equals(this)) {
				continue;
			}
			if(Point.distance(g.core, this.core) <= eps) {
				ret.add(g);
			}
		}
		return ret.toArray(new Group[0]);
	}

	public static Group newGroup(Point x, double eps) {
		Group g = new Group();
		g.core = x;
		g.points = new LinkedList<>();
		// add reachable groups to points
		Point[] points = findNeighbours(x, eps, g);
		g.points.addAll(Arrays.asList(points));

		groups.add(g);
		return g;
	}

	/**
	 * @return 返回的值中包括p自己
	 */
	static Point[] findNeighbours(Point p, double eps, Group g) {
		Set<Point> set = new HashSet<>();
		set.add(p);
		if(Point.distance(p, g.core) <= eps/2) {
			// cannot Arrays.asList(g.points)
			for(Point point : g.points) {
				set.add(point);
			}
		} else {
			for(Point point : g.points) {
				if(Point.distance(p, point) <= eps) {
					set.add(point);
				}
			}
		}

		Group[] nearbyGroups = g.nearbyGroups(eps);
		for(Group group : nearbyGroups) {
			// continue For reduce indentation
			if(!(Point.distance(group.core, g.core) <= Point.distance(group.core, p) + eps + Point.distance(g.core, p))) {
				continue;
			}
			for(Point point : group.points) {
				if(Point.distance(point, p) <= eps) {
					set.add(point);
				}
			}
		}
		return set.toArray(new Point[0]);
	}

	public static List<Group> groups = new LinkedList<>();
	// ||Sm-X|| <= eps
	public static Group cover(Point p, double eps) {
		for(Group g : groups) {
			if(Point.distance(g.core, p) <= eps) {
				return g;
			}
		}
		return null;
	}
	// ||Sm-X|| <= 2*eps
	public static Group cover2(Point p, double eps) {
		for(Group g : groups) {
			if(Point.distance(g.core, p) <= 2*eps) {
				return g;
			}
		}
		return null;
	}
}

class Util {
	// Online testing can not enable assertions
	public static void assume(Boolean expression) {
		assume(expression, "Expression Is Not True.");
	}
	public static void assume(Boolean expression, String reason) {
		if(expression==null || expression==false) {
			if(reason != null)
				throw new AssertionError(reason);
			else
				throw new AssertionError();
		}
	}
}
